//基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。 
//
// 假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。 
//
// 
// 例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。 
// 
//
// 另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中） 
//
// 给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成
//此基因变化，返回 -1 。 
//
// 注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。 
//
// 
//
// 示例 1： 
//
// 
//输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
//输出：1
// 
//
// 示例 2： 
//
// 
//输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA",
//"AAACGGTA"]
//输出：2
// 
//
// 示例 3： 
//
// 
//输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC",
//"AACCCCCC"]
//输出：3
// 
//
// 
//
// 提示： 
//
// 
// start.length == 8 
// end.length == 8 
// 0 <= bank.length <= 10 
// bank[i].length == 8 
// start、end 和 bank[i] 仅由字符 ['A', 'C', 'G', 'T'] 组成 
// 
//
// Related Topics 广度优先搜索 哈希表 字符串 👍 288 👎 0


package LeetCode.editor.cn;

import java.util.*;

/**
 * @author ldltd
 * @date 2024-05-20 23:52:43
 * @description 433.最小基因变化
 */
public class MinimumGeneticMutation{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 MinimumGeneticMutation fun=new MinimumGeneticMutation();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	public int minMutation(String start, String end, String[] bank) {
		Set<String> cnt = new HashSet<String>();
		Set<String> visited = new HashSet<String>();
		char[] keys = {'A', 'C', 'G', 'T'};
		for (String w : bank) {
			cnt.add(w);
		}
		if (start.equals(end)) {
			return 0;
		}
		if (!cnt.contains(end)) {
			return -1;
		}
		Queue<String> queue = new ArrayDeque<String>();
		queue.offer(start);
		visited.add(start);
		int step = 1;
		while (!queue.isEmpty()) {
			int sz = queue.size();
			for (int i = 0; i < sz; i++) {
				String curr = queue.poll();
				for (int j = 0; j < 8; j++) {
					for (int k = 0; k < 4; k++) {
						if (keys[k] != curr.charAt(j)) {
							StringBuffer sb = new StringBuffer(curr);
							sb.setCharAt(j, keys[k]);
							String next = sb.toString();
							if (!visited.contains(next) && cnt.contains(next)) {
								if (next.equals(end)) {
									return step;
								}
								queue.offer(next);
								visited.add(next);
							}
						}
					}
				}
			}
			step++;
		}
		return -1;
	}

	Map<Character, Integer> mp=new HashMap<>();


	public int minMutation1(String startGene, String endGene, String[] bank) {
		mp.put('A', 1);
		mp.put('C', 2);
		mp.put('T', 3);
		mp.put('G', 4);
		Deque<Integer> q=new ArrayDeque<>();
		int []ar=new int [bank.length];
		for(int i=0;i<bank.length;i++){
			ar[i]=convert(bank[i]);
		}
		int l=convert(startGene);
		int r=convert(endGene);
		Map<Integer,Integer> map=new HashMap<>();
		q.offer(l);
		int step=0;
		map.put(l,0);
		while(!q.isEmpty()){
			l=q.poll();
			step=map.get(l);
			if(l==r)  return step;
			for(int i=0;i<bank.length;i++){
				if(map.containsKey(ar[i]))
					continue;
				double t=Math.abs(l-ar[i]);

				while(t>=10)  t/=10.0;
				if((t==1||t==2||t==3)){
					map.put(ar[i],step+1);
					q.offer(ar[i]);
				}
			}
		}
		return -1;
	}

	public int convert(String s){
		int res=0;
		for(char c:s.toCharArray()){
			res+=mp.get(c);
			res*=10;
		}
		return res/10;
	}

	public int minMutation2(String start, String end, String[] bank) {
		if(start.equals(end)){return 0;}
		int ans=0;
		boolean used[]=new boolean[bank.length];
		for(int i=0;i<bank.length;i++){if(start.equals(bank[i])){used[i]=true;}}
		Queue<String> q=new LinkedList<>();
		q.add(start);
		while(q.size()>0){
			ans++;
			int size=q.size();
			for(int i=0;i<size;i++){
				String s=q.poll();
				for(int j=0;j<bank.length;j++){
					if(!used[j]&&numOfDifference(s,bank[j])==1){
						if(end.equals(bank[j])){return ans;}
						used[j]=true;
						q.add(bank[j]);
					}
				}
			}
		}
		return -1;
	}
	public int numOfDifference(String s1,String s2){
		char c1[]=s1.toCharArray(),c2[]=s2.toCharArray();
		int count=0;
		for(int i=0;i<c1.length;i++){if(c1[i]!=c2[i]){count++;}}
		return count;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
